#pragma once
#include "hash_prime.h"
#include <string.h>
#ifndef WIN32
#if defined (CCORE_MAC)
#include <algorithm>
#else
#include <bits/move.h>
#endif
#endif

namespace qb{
	namespace base{
		/*
			模板参数要求:
			类Key必须有如下成员
			bool operator==(const Key& key)const;
			用于判定两个Key对象是否是一个对象,是否相等
			*/
		template<class Entry, class Key>
		class KeyHashMap{
			typedef unsigned int HashCode;
		public:
			class Listener{
			public:
				virtual void OnEntry(Entry* entry, int slot){}
			};
			struct EntrySlot{
				int		count;
				Entry*	head;
			};
		protected:
			EntrySlot*		m_slots;			// 哈希插槽
			int				m_length;			// 哈西插槽的长度，通常为质数
			int				m_count;			// 实际个数
			int				m_capcity;
			double			m_expand_ratio;
		public:
			KeyHashMap() :m_length(0), m_count(0), m_slots(0), m_expand_ratio(2.0), m_capcity(0){}
			~KeyHashMap(){ if (m_slots) { delete[] m_slots; m_slots = 0; } }
			int GetLength()const{ return m_length; }
			int GetCount()const{ return m_count; }
			int GetBytes()const{ return sizeof(*this) + m_length*sizeof(Entry*); }
			double GetLoadFactor()const{ return m_length <= 0 ? 0 : (m_count *1.0 / m_length); }
			void SetExpandRatio(double ratio){
				m_expand_ratio = ratio <= 1 ? 1 : ratio;
				m_capcity = m_length*m_expand_ratio;
			}
			int CalcCount()const{
				int ntotal = 0;
				for (int i = 0; i < m_length; i++){
					Entry* head = m_slots[i].head;
					while (head)
					{
						ntotal++;
						head = head->hashnext;
					}
				}
				return ntotal;
			}
			Entry* GetHead(int i){
				if (i >= 0 && i < m_length && m_slots)
					return m_slots[i].head;
				return nullptr;
			}
			void Build(int length)
			{
				length = length < 32 ? 32 : length;
				m_count = 0;
				m_length = length;
				m_capcity = (int)(length*m_expand_ratio);
				m_slots = new EntrySlot[m_length];
				memset(m_slots, 0, m_length*sizeof(EntrySlot));
			}
			void Clear(){ memset(m_slots, 0, m_length*sizeof(EntrySlot)); m_count = 0; }
			void Enum(Listener* listener)const{
				for (int i = 0; i < m_length; i++)
				{
					Entry* first = m_slots[i].head;
					while (first)
					{
						Entry* next = first->hashnext;
						listener->OnEntry(first, i);
						first = next;
					}
				}
			}
			void Expand(int length)
			{
				KeyHashMap temp;
				temp.Build(length);
				for (int i = 0; i < m_length; i++)
				{
					Entry* first = m_slots[i].head;
					while (first)
					{
						Entry* next = first->hashnext;
						HashCode hash = first->key.GetHash();
						first->hashprev = first->hashnext = 0;
						temp.Insert(first, hash);
						first = next;
					}
				}
				Swap(temp);
			}
			Entry* Find(const Key& key)const
			{
				return Find(key, key.GetHash());
			}
			Entry* Find(const Key& key, HashCode hash)const
			{
				int npos = hash%m_length;
				Entry* first = m_slots[npos].head;
				while (first)
				{
					if (first->key == key)
						return first;
					first = first->hashnext;
				}
				return nullptr;
			}
			void Insert(const Key& key, Entry* entry)
			{
				Insert(entry, key.GetHash());
			}
			void Insert(Entry* entry, HashCode hash)
			{
				int npos = hash%m_length;
				Entry* first = m_slots[npos].head;
				m_slots[npos].head = entry;
				m_slots[npos].count++;
				entry->hashprev = nullptr;
				entry->hashnext = first;
				if (first)
					first->hashprev = entry;
				m_count++;
				if (m_count > m_capcity)
				{
					Expand(GetHashPrimeLargerThan(m_length + m_count));
				}
			}
			Entry* Remove(const Key& key, HashCode hash)
			{
				int npos = hash%m_length;
				Entry* first = m_slots[npos].head;
				while (first)
				{
					if (first->key == key)
					{
						Entry* prev = first->hashprev;
						Entry* next = first->hashnext;
						if (prev)
							prev->hashnext = next;
						if (next)
							next->hashprev = prev;
						if (first == m_slots[npos].head)
							m_slots[npos].head = next;
						first->hashnext = first->hashprev = 0;
						m_slots[npos].count--;
						m_count--;
						return first;
					}
					first = first->hashnext;
				}
				return 0;
			}
			Entry* Remove(const Key& key)
			{
				return Remove(key, key.GetHash());
			}
			Entry* GetSlot(int islot)
			{
				if (islot >= 0 && islot < m_length && m_slots)
					return m_slots[islot].head;
				return nullptr;
			}
		protected:
			void Swap(KeyHashMap& hashList)
			{
				std::swap(m_slots, hashList.m_slots);
				std::swap(m_length, hashList.m_length);
				std::swap(m_count, hashList.m_count);
				std::swap(m_capcity, hashList.m_capcity);
				std::swap(m_expand_ratio, hashList.m_expand_ratio);
			}
		};
	}//namespace base;
}//namespace ss;
